#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    int maxTotalReward(vector<int>& rewardValues) {
        sort(rewardValues.begin(), rewardValues.end());
        int n = rewardValues.size();
        const int N = 4010;
        int max1 = rewardValues[n - 1];
        max1 *= 2;
        vector<bool> dp(N, false);
        dp[0] = true;
        for (int i = 1; i <= n; i++)
        {
            for (int j = rewardValues[i - 1]; j <= max1; j++)
            {
                if (dp[j - rewardValues[i - 1]] == true && 2 * rewardValues[i - 1] > j) dp[j] = true;
            }
        }
        for (int i = max1; i >= 1; i--)
        {
            if (dp[i] == true) return i;
        }
        return -1;
    }
};